CSE 311: Section 1

Task 1 – Equivalences

Prove that each of the following equivalences using an equivalence chain.

1. $(p \to \neg p) \land (\neg p \to p) \equiv \textsf{F}$

2. $\neg p \rightarrow (q \rightarrow r)\equiv q \rightarrow (p \vee r)$

3. $\lnot(q\lor p) \lor \lnot(r\lor \lnot p)\to p\equiv p\lor q$

4. $p \leftrightarrow q\equiv (p \wedge q) \vee (\neg p \wedge \neg q)$
   Hint: You may use the definition of biconditional that $p \leftrightarrow q \equiv (p\rightarrow q) \wedge (q \rightarrow p)$.

Task 2 – Welcome to the $\forall LL\exists n$ School!

Prove the following assertions using a sequence of logical equivalences.

In addition to Cozy's documentation, a reference sheet of logical equivalences is on the website.

Hints: For equivalences where one side is much longer than the other, a good heuristic is to start with the longer side and try to apply the rules that will shorten it. In some cases, it may work better to work to shorten both sides to the same expression and then combine those two sequences into one.

1. $(\neg P \to P) \to \neg P \equiv \neg P$

2. $(\neg P \to R) \wedge (\neg Q \to P) \equiv \neg P \to (Q \wedge R)$

Cozy's documentation for equivalence proof problems is available here.

In short: select the rule to apply and a direction — either replacing the left-side with the right-side (“left-to-right”) or vice versa (“right-to-left”) – and then click “Apply”.¹ Cozy will apply the rule and produce resulting formula on the line. You can work forward from the top formula or backward from the bottom formula or both! The chain is complete when the two sides reach the same formula.

Let the domain of discourse be all students and classes at UW. Define the predicates $\textsf{CS}(x)$ to mean that $x$ majors in CS (presumably $x$ is a student) and $\textsf{CE}(x)$ to mean that $x$ majors in CE (presumably $x$ is a student). Define the predicates $\textsf{CSE}(y)$ to mean that $y$ is a CSE class (presumably $y$ is a class) and $\textsf{MATH}(y)$ to mean that $y$ is a MATH class (presumably $y$ is a class). Define the predicate $\textsf{Wants}(x, y)$ to mean that $x$ wants to take $y$ (presumably $x$ is a student and $y$ is a class), the predicate $\textsf{Likes}(x, y)$ to mean that $x$ likes $y$ (presumably $x$ is a student and $y$ is a class), and the predicate $\textsf{HasToTake}(x, y)$ to mean that $x$ has to take $y$ (presumably $x$ is a student and $y$ is a class).

Translate each of the following logical statements into English. You should not simplify. However, you should use the techniques shown in lecture for producing more natural translations when restricting domains and for avoiding the introduction of variable names when not necessary.

1. $\neg \exists x \, (\textsf{CS}(x) \wedge \textsf{CE}(x))$

2. $\exists x\, \big(\textsf{CS}(x) \wedge \exists y\, (\textsf{CSE}(y) \wedge \neg \textsf{HasToTake}(x,y) \wedge \textsf{Likes}(x,y) )\big)$

3. $\forall x\, \big(\textsf{CE}(x) \to \exists y\, (\textsf{MATH}(y) \wedge \textsf{HasToTake}(x,y))\big)$

4. $\exists x\, \big((\textsf{CS}(x) \lor \textsf{CE}(x)) \wedge \forall y\, (\textsf{CSE}(y) \to \textsf{Wants}(x, y))\big)$

Task 3 – Translate to Logic

Express each of these system specifications using predicates, quantifiers, and logical connectives. For some of these problems, more than one translation will be reasonable depending on your choice of predicates.

1. Every user has access to an electronic mailbox.

2. The system mailbox can be accessed by everyone in the group if the file system is locked.

3. The firewall is in a diagnostic state only if the proxy server is in a diagnostic state.

4. At least one router is functioning normally if the throughput is between 100kbps and 500 kbps and the proxy server is not in diagnostic mode.

Task 4 – The Calm Before the Form

The Java project you are working on contains the following function. It takes four boolean arguments, $a$, $b$, $c$, and $d$, and calculates some boolean function of them called $E$:

    public static boolean E(boolean a, boolean b, boolean c, boolean d) {
      if (!(a || b))
        return false;
      if (!(!a || !b))
        return false;
      if (!(a || c))
        return false;
      return (b || !d);
    }

The code checks the value of the four disjunctions $a \vee b$, $\neg a \vee \neg b$, $a \vee c$, and $b \vee \neg d$ and returns true iff all four of them are true. In other words, it calculates the conjunction (and) of those four expressions. Specifically, it calculates the same value as the following (non-canonical) CNF expression: $$(a \vee b) \wedge (\neg a \vee \neg b) \wedge (a \vee c) \wedge (b \vee \neg d)$$

Note that this Java code could be written equivalently as a single return statement:

      return (a || b) && (!a || !b) && (a || c) && (b || !d);

The Java compiler would automatically translate that into the series of if statements above that returns false as soon as one disjunction is found to evaluate as false, a process known as “short circuiting”.

1. Write a truth table for $E$. Include columns for $a$, $b$, $c$, $d$, all four disjunctions, and $E$.

2. Write the canonical DNF expression for $E$.

3. Translate your DNF expression into a new Java implementation of E.

   Like above, your code should be a series of if statements and then a return, except that, now, each if should check the value of a conjunction and return true if it is true.

   (Do not simplify. Translate your expression to code in the most direct way possible.)